NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/std/c/718

Internet Message Format | 1996-08-06 | 5KB

Path: mail2news.demon.co.uk!genesis.demon.co.uk
From: Lawrence Kirby <[e-mail]>
Newsgroups: comp.std.c
Subject: Re: Restrictions on qsort compare function?
Date: Tue, 09 Apr 96 16:51:22 GMT
Organization: none
Message-ID: <[e-mail]>
References: <4kbl1l$[e-mail]>
Reply-To: [e-mail]
X-NNTP-Posting-Host: genesis.demon.co.uk
X-Newsreader: Demon Internet Simple News v1.27
X-Mail2News-Path: genesis.demon.co.uk

In article <4kbl1l$[e-mail]>
           [e-mail] "Peter Curran" writes:

>On Mon, 08 Apr 96 13:56:53 GMT in article <[e-mail]>
>    Lawrence Kirby <[e-mail]> (Lawrence Kirby) wrote:
>
>>>IMHO, qsort() is required to return an array that is sorted according to the
>>>criteria implied by the comparison function.  That is, at the point where
> qsort
>>>returns, the array must match the order implied by the comparison function.
>
>The comparison function I postulated *is* consistent, at any instant in time.

Unless it is consistent over the entire duration of the sort (it defines
the sorted ordering of the elements subject to equal keys) it doesn't
form a valid relation for a sort.

>(Just to be clear - another correspondent suggested my original posting may not
>have said quite what I intended.  The comparison function I suggested., or
>intended, calculates as result by comparison of the values pointed at by the
>parameters, in a way we can all agree is acceptable.  However, it then calls
>time(), and if the result it odd it negates the result before returning it.  In
>a conventional implementation of time(), it reverses the order every second,
> but
>defines a consistent order at any given time.)

Or use rand()! However the relation is defined purely on the values of the
keys. The standard embodies this idea too -

"The function shall return an integer less than, equal to, or greater than
 zero if the first argument is considered to be respectively less than, equal
 to, or greater than the second"

gives no license for the comparison function to consider anything other than
its arguments in determining the return value. I would certainly accept that
this is worded badly i.e. "first argument" should read "object pointed to by
the first argument" and similarly for "second". However this loose usage
appears elsewhere in the standard and I believe the intent is clear (I'm
happy to discuss that further).

>>The critical word is 'sorted'. I suggest you read section 5 (i.e. the
>>first section of chapter 5) in Knuth Vol 3 to get a reasonable idea of what
>>a sort is.
>
>I can assure you that I read Knuth cover to cover, within a few weeks of its
>first publication.  I really don't think this kind of insult is necessary here.

No insult was intended - apologies, I could have written that better.
My point stands though that sorting is a well defined concept and there
is every reason to assume that a formal standards document will use terms in
their correct or formal sense. Otherwise they don't have any well-defined
meaning at all.

>There isn't much point in continuing this.  We will have to agree to disagree.
>I understand how you are reaching the conclusions you are reaching (and I agree
>it should be possible to reach them).  However I think that you are stretching
>the text of the standard beyond the breaking point to get there.

My argument is based fundamentally on 3.16:

"Undefined behaviour is otherwise indicated in this International Standard
 by the words ``undefined behaviour'' or by the omission of any explicit
 defintion of behaviour. There is no difference in emphasis among these
 three; they all describe ``behaviour that is undefined.''"

This means that code has undefined behaviour unless you can show what the
defined behaviour is according to the standard. In all of your examples
the behaviour can vary depending on the actual implementation of qsort().
In the absense of any other limitation in the standard (such as a statement
of implementation-defined behaviour), this means the behaviour is undefined.

To disprove my assertion for any of your examples the bottom line is to
show, by reference to the standard, what the defined behaviour is. An
example is putting forward a reasonable definition of 'sort' which would
make the example well defined.

Something else to consider is that the bsearch() function defines a
comparison function in essentially the same way as the qsort() function
does (except that it refers correctly to the key object and array element
rather than just 'arguments'), so a valid qsort() comparison function
ought to be a valig bsearch() comparison function.

--
-----------------------------------------
Lawrence Kirby | [e-mail]
Wilts, England | [e-mail]
-----------------------------------------